package LeetCode.TwoPointers;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author : LdLtd
 * @Date : 2023/7/23
 * @Description:15.三数之和
 */
public class ThreeSum {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] ints = {0, 0, 0, 0};
        System.out.println(solution.threeSum(ints));
    }

    static class Solution {

        /*复杂度高  超时*/
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
//            Map<Integer, Integer> map = IntStream.range(0, nums.length)
//                    .boxed()
//                    .sorted(Comparator.comparingInt(i -> nums[i])) // 使用sorted()方法进行排序
//                    .collect(Collectors.toMap(index -> index, index -> nums[index], (a, b) -> a, HashMap::new));
            Arrays.sort(nums);
            int l = 0, r = nums.length - 1, ll, rr, sum, t;
            ll = nums[l];
            rr = nums[r];
            while (l + 1 < r && ll <= 0 && rr >= 0) {
                ll = nums[l];
                rr = nums[r];
                //如果最大的数相加正的太多 -2 + 8  6
                if ((ll + rr) > 0 && ll + rr > -ll) {
                    r--;
                    //如果最大的数相加都负的多，-8 + 2 -6
                } else if ((ll + rr) < 0 && ll + rr > -rr) {
                    l++;
                } else {
                    t = 0 - ll - rr;
                    for (int i = l + 1; i < r; i++) {
                        if (t == nums[i]) {
                            res.add(new ArrayList<Integer>(Arrays.asList(ll, rr, t)));
                            break;
                        }
                    }
                    if (t > 0) {
                        while (l < r && nums[l] == nums[l + 1]) {
                            l++;
                        }
                        l++;
                    } else {
                        while (l < r && nums[r] == nums[r - 1]) {
                            r--;
                        }
                        r--;
                    }
                }
            }
            return res;
        }

        public List<List<Integer>> threeSum1(int[] nums) {
            //定义一个结果集
            List<List<Integer>> res = new ArrayList<>();
            //数组的长度
            int len = nums.length;
            //当前数组的长度为空，或者长度小于3时，直接退出
            if (nums == null || len < 3) {
                return res;
            }
            //将数组进行排序
            Arrays.sort(nums);
            for (int i = 0; i < len; i++) {
                //如果遍历的起始元素大于0，就直接退出
                //原因，此时数组为有序的数组，最小的数都大于0了，三数之和肯定大于0
                if (nums[i] > 0) {
                    break;
                }
                //去重，当起始值等于前一个元素，得到的结果和前一次相同
                if (i > 0 && nums[i] == nums[i - 1]) continue;
                int l = i + 1;
                int r = len - 1;
                //当 l 不等于 r时就继续遍历
                while (l < r) {
                    int sum = nums[i] + nums[l] + nums[r];
                    //如果等于0，将结果对应的索引位置的值加入结果集中
                    if (sum == 0) {
                        res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                        //移动左右指针的时候，先判断，如果重复直接跳过
                        //去重，因为i不变，当此时l取值与前一个相同，不用重复计算
                        while (l < r && nums[l] == nums[l + 1]) {
                            l++;
                        }
                        //去重，因为 i不变，当此时 r 取的数的值与前一个相同，所以不用在计算
                        while (l < r && nums[r] == nums[r - 1]) {
                            r--;
                        }
                        //将 左指针右移，将右指针左移。
                        l++;
                        r--;
                        //如果结果小于0，将左指针右移
                    } else if (sum < 0) {
                        l++;
                        //如果结果大于0，将右指针左移
                    } else if (sum > 0) {
                        r--;
                    }
                }
            }
            return res;
        }
    }
}
